#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#define SIZE 1006
#define MAX 2006

int map[SIZE][SIZE];
int d[SIZE];
int mark[SIZE];
int n, m;

int dijkstra(int from, int to)
{	

    int i = 0, j = 0;
    for (i = 1; i <= n; i++) {
        mark[i] = 0;
        d[i] = map[from][i];
    }
    for (i = 1; i < n; ++i) {
        int min = MAX;
        int pos = 0;

        for (j = 1; j <= n; ++j) {
            if (!mark[j] && min > d[j]) {
                pos = j;
                min = d[j];
            }
        }
        mark[pos] = 1;

        for (j = 1; j <= n; ++j) 
        {
            if (!mark[j] && (d[j] > (d[pos] + map[pos][j]))) 
            { 
                d[j] = d[pos] + map[pos][j];
            }
        }
    }

    return d[to];
}

int main() {

    int i, j;
    int temp = MAX;

    scanf("%d%d",&n,&m);

    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= n; ++j)
        {
            map[i][j] = MAX;
        }
    }

    int a,b,c;
    for (i = 1; i <= m; ++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        map[a][b] = map[b][a] = c;
    }
    
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= n; ++j)
        {
            if (map[i][j] == temp)
                map[i][j] = map[j][i];
        }
    }
    int len = dijkstra(1, n);

    printf("%d", len);

    return 0;
}
